Ich habe vor als Seminarthema die Particle Swarm Optimization (PSO) zu wählen, die von Kennedy und Eberhart im Jahre 1995 entwickelt wurde. Das PSO gehört zu den globalen Optimierungsverfahren und hat den Vorteil, dass sie lediglich eine Funktion auswerten können muss, um diese zu optimieren. Im Normalfall ist das Ziel einer solchen Optimierung, das Finden der Stelle, die die gegebene Funktion minimiert. Das PSO versucht dabei zufällige Punkte im Dimensionsraum auszuwerten und sich mit einem iterativen Verfahren dem globalen Minimum zu nähern. Entstanden ist das Optimierungsverfahren beim Analysieren von Vogelschwärmen, die sich durch den Himmel bewegen und hat schnell die ersten Anwendungen in der Teilchenphysik beim Simulieren von Teilchenbewegungen gefunden. Anschließend wurde es auch von anderen Fachgebieten wie der Finanzmathematik adaptiert, um sehr komplexe Probleme zu lösen, für die es keine geschlossenen Formen gibt.
Zu minimieren ist eine Zielfunktion \(f:\mathbb{R}^N \rightarrow \mathbb{R}\) die auf einem Gebiet \(G \subset \mathbb{R}^N\) definiert ist. Dabei initialisiert das PSO zufällige Positionen \(x_d\) im Gebiet \(G\), welche Particle genannt werden. Jeder dieser Particle hat eine eigene Geschwindigkeit \(v_d\), die anfänglich zufällig generiert wird. Zusätzlich speichert jedes Particle die beste Position, die es bisher besucht hat in \(P_d\) und die beste Position aller Particle wird in \(p_g\) gespeichert. Danach werden die Particle mit den folgenden zwei Formeln verschoben (\(i \rightarrow i+1\)): \[\begin{align*} v_d^{i+1} &= wv_d^{i} + c_p r_1^i (P_d^i - x_d^i) + c_g r_2^i (p_g^i - x_d^i) \\ x_d^{i+1} &= x_d^i + v_d^{i+1} \end{align*}\] Dabei sind \(c_p\), \(c_g\) und \(w\) wählbare Hyperparameter und \(r_1\) und \(r_2\) sind gleichverteilte Zufallszahlen in \([0,1]\). Nach jeder Iteration wird die Zielfunktion mit den neuen Positionen ausgewertet und die Positionen in \(P_d\) und \(p_g\) gegebenenfalls geupdated. Diese Iteration wird so lange durchgeführt, bis eine Abbruchbedingung erreicht wird.
Das PSO ist im Gegensatz zu manch anderen Optimierungsverfahren im
\(\mathbb{R}^2\) sehr schön
visualisierbar, indem man die Bewegungen der einzelnen Particle
verfolgen kann. Dies kann mithilfe des nachfolgenden Beispiels gezeigt
werden.
Ziel sei es folgende Funktion im Gebiet \([-10, 10]^2\) zu minimieren:
fn <- function(pos){
-20 * exp(-0.2 * sqrt(0.5 *((pos[1]-1)^2 + (pos[2]-1)^2))) -
exp(0.5*(cos(2*pi*pos[1]) + cos(2*pi*pos[2]))) +
exp(1) + 20
}Die nachfolgende Simulation zeigt die Bewegungen aller Particle im Schwarm:
Informationen zur Bedienung:
- Linke und Rechte Maustate halten und dann die Maus bewegen kann
genutzt werden, um die Kamera im Raum zu drehen.
- Das Mausrad kann zum Zoomen verwendet werden.
- Der Play-Button startet die Simulation und kann durch Drücken auf den
Iterationsbalken gestoppt werden.
Der größte Unterschied zu anderen Optimierungsverfahren sind die niedrigen Vorraussetzungen und das keine Ableitung der Zielfunktion benötigt wird. Natürlich liefert das PSO nicht immer die globale Lösung als Ergebnis, aber oft eine ausreichend gute Näherung.
Ich bin der Meinung das jeder Mathematiker schonmal ein PSO gesehen
haben sollte, um beispielsweise andere Optimierungsverfahren zu
evaluieren oder überhaupt eine Chance zu haben eine Lösung zu finden.
Deshalb ist die Stärke des PSO’s auch genau da, wo es kaum andere
Möglichkeiten gibt an eine ausreichend gute Lösung zu kommen. Ein
anderer Aspekt ist die Simplizität und die schöne Visualisierbarkeit,
die es meinen Kommilitonen vielleicht spannender macht meinem Thema auch
gehör zu schenken. Zusätzlich habe ich ebenfalls vor eine Art WebApp zu
erstellen, in der jeder seine eigene Funktion eingeben kann und diese
wird dann vom PSO versucht zu minimieren.